package cn.suchan.jianzhi.q24_tree;

import java.util.ArrayList;
import java.util.Collections;

/**
 * 知识点：二叉树中和为某一值的路径
 * 题目描述
 * 输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。
 * 路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
 * (注意: 在返回值的list中，数组长度大的数组靠前)
 *
 * @author suchan
 * @date 2019/05/28
 */
public class Solution {
    /**
     * 存放所有路径
     */
    ArrayList<ArrayList<Integer>> paths = new ArrayList<>();
    /**
     * 用于遍历
     */
    ArrayList<Integer> nodes = new ArrayList<>();
    /**
     * 节点值之和
     */
    int sum = 0;

    /**
     * 这个是根据FindPath2()修改的，想要保留一下FindPath2()，所以就写了两个方法
     * 我这个方法借助太多中间值了，所以效率不会这么高
     *
     * @param root
     * @param target
     * @return
     */
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        if (root == null || target < root.val) {
            return new ArrayList<>();
        }

        // 存放每个树节点
        ArrayList<TreeNode> treeList = new ArrayList();
        treeList.add(root);
        // 存放根节点的值
        ArrayList<Integer> nodeList = new ArrayList<>();
        nodeList.add(root.val);
        // 存放从根节点到任意叶子结点的路径
        ArrayList<ArrayList<Integer>> nodePath = new ArrayList<>();
        nodePath.add(nodeList);
        for (int i = 0; i < treeList.size(); i++) {
            if (treeList.get(i).left != null || treeList.get(i).right != null) {
                if (treeList.get(i).left != null) {
                    treeList.add(treeList.get(i).left);
                    ArrayList<Integer> tempPath = new ArrayList<>();
                    tempPath.addAll(nodePath.get(0));
                    tempPath.add(treeList.get(i).left.val);
                    nodePath.add(tempPath);
                }
                if (treeList.get(i).right != null) {
                    treeList.add(treeList.get(i).right);
                    ArrayList<Integer> tempPath = new ArrayList<>();
                    tempPath.addAll(nodePath.get(0));
                    tempPath.add(treeList.get(i).right.val);
                    nodePath.add(tempPath);
                }
                nodePath.remove(nodePath.get(0));
            }
        }
        ArrayList<ArrayList<Integer>> resultList = new ArrayList();
        for (int i = 0; i < nodePath.size(); i++) {
            int result = target;
            for (Integer node : nodePath.get(i)) {
                result = result - node;
            }
            if (result == 0) {
                resultList.add(nodePath.get(i));
            }
        }
        // path长度大的在前
        Collections.sort(resultList, (path1, path2) -> {
            //相等  0 ,小于  -1, 大于  1
            if (path1.size() > path2.size()) {
                return -1;
            }
            return 1;
        });

        return resultList;
    }

    /**
     * 这是参照别人的写法，使用了递归进行实现，效率更高点
     *
     * @param root
     * @param target
     * @return
     */
    public ArrayList<ArrayList<Integer>> FindPath1(TreeNode root, int target) {

        if (root == null) {
            return paths;
        }
        sum += root.val;
        nodes.add(root.val);

        // 如果此时路径长度值刚好等于目标值，并且此时所在结点为叶子结点
        // (路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径),路径存入lists
        if (sum == target && root.left == null && root.right == null) {
            // 存放路径结点值
            ArrayList<Integer> path = new ArrayList<>();
            path.addAll(nodes);
            paths.add(path);
        } else if (sum < target) {
            // 先遍历左子树
            if (root.left != null) {
                FindPath1(root.left, target);
            }
            // 左子树遍历结束，遍历右子树
            if (root.right != null) {
                FindPath1(root.right, target);
            }
        }

        // 去掉这个结点值
        sum -= root.val;
        // 删除该结点，返回到父结点
        nodes.remove(nodes.size() - 1);
        return paths;
    }

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(17);
        TreeNode node8 = new TreeNode(8);
        TreeNode node9 = new TreeNode(9);
        TreeNode node10 = new TreeNode(10);
        TreeNode node11 = new TreeNode(11);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node4.left = node8;
        node4.right = node9;
        node5.left = node10;
        node6.left = node11;

        Solution solution = new Solution();
        // System.out.println("我的==>" + solution.FindPath(node1, 4));
        // System.out.println("他的==>" + solution.FindPath1(node1, 4));
        //System.out.println("啦啦==>" + solution.FindPath2(node1, 4));
        //System.out.println("我的==>" + solution.FindPath(node1, 21));
        System.out.println("他的==>" + solution.FindPath1(node1, 21));
        //System.out.println("啦啦==>" + solution.FindPath2(node1, 21));
    }

    /**
     * 我这个写法的路径表示跟题目描述的不太一样，而是从根节点到任意节点，不一定是叶子结点
     *
     * @param root
     * @param target
     * @return
     */
    /*public ArrayList<ArrayList<Integer>> FindPath2(TreeNode root, int target) {
        if (root == null || target < root.val) {
            return new ArrayList<>();
        }

        // 存放每个树节点
        ArrayList<TreeNode> treeList = new ArrayList();
        treeList.add(root);
        // 存放根节点的值
        ArrayList<Integer> nodeList = new ArrayList<>();
        nodeList.add(root.val);
        // 存放从根节点到任意节点的路径
        ArrayList<ArrayList<Integer>> pathList = new ArrayList<>();
        pathList.add(nodeList);

        for (int i = 0; i < treeList.size(); i++) {
            if (treeList.get(i).left != null) {
                treeList.add(treeList.get(i).left);
                ArrayList<Integer> tempPath = new ArrayList<>();
                tempPath.addAll(pathList.get(i));
                tempPath.add(treeList.get(i).left.val);
                pathList.add(tempPath);
            }
            if (treeList.get(i).right != null) {
                treeList.add(treeList.get(i).right);
                ArrayList<Integer> tempPath = new ArrayList<>();
                tempPath.addAll(pathList.get(i));
                tempPath.add(treeList.get(i).right.val);
                pathList.add(tempPath);
            }
        }
        ArrayList<ArrayList<Integer>> resultList = new ArrayList();
        for (int i = 0; i < pathList.size(); i++) {
            int result = target;
            for (Integer node : pathList.get(i)) {
                result = result - node;
            }
            if (result == 0) {
                resultList.add(pathList.get(i));
            }
        }
        // path长度大的在前
        Collections.sort(resultList, (path1, path2) -> {
            //相等  0 ,小于  -1, 大于  1
            if (path1.size() > path2.size()) {
                return -1;
            }
            return 1;
        });

        return resultList;
    }*/


}
